package day0308

import (
	"math"
)

func jump(nums []int) int {
	n := len(nums)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = math.MaxInt64
	}
	dp[0] = 0
	for i := 0; i < n; i++ {
		t := nums[i]
		k := dp[i]
		for j := i + 1; j < n && j <= i+t; j++ {
			dp[j] = min(k+1, dp[j])
		}
	}
	return dp[n-1]
}

func min(x, y int) int {
	if x >= y {
		return y
	}
	return x
}
